' Written by Craig'n'Dave
Module Module1
    ' Merge sort using iteration
    Function merge_sort(items() As String)
        ' Split step
        Dim items_list As New List(Of List(Of String))
        items_list = split(items)

        ' Merge step
        Dim index As Integer
        Dim new_list As List(Of String)
        Do While items_list.Count <> 1
            index = 0
            ' Merge pairs of lists
            Do While index < items_list.Count - 1
                new_list = merge(items_list(index), items_list(index + 1))
                items_list(index) = new_list
                ' Once merged, delete one of the now redundant lists
                items_list.RemoveAt(index + 1)
                index = index + 1
            Loop
        Loop
        Return items_list(0).ToArray
    End Function

    Function split(items() As String)
        ' Every item is put into it's own list within a container list
        Dim list_of_items As New List(Of List(Of String))
        Dim item As List(Of String)
        Dim index As Integer
        ' Every item is put into it's own list within a container list
        For index = 0 To items.Count - 1
            item = New List(Of String)
            item.Add(items(index))
            list_of_items.Add(item)
        Next
        Return list_of_items
    End Function

    Function merge(list1 As List(Of String), list2 As List(Of String))
        ' Merge two lists into a new list
        Dim new_list As New List(Of String)
        Dim index1 As Integer = 0
        Dim index2 As Integer = 0
        ' Check each item in each list, and add the smallest item to a new list
        Do While index1 < list1.Count And index2 < list2.Count
            If list1(index1) > list2(index2) Then
                new_list.Add(list2(index2))
                index2 = index2 + 1
            ElseIf list1(index1) < list2(index2) Then
                new_list.Add(list1(index1))
                index1 = index1 + 1
            ElseIf list1(index1) = list2(index2) Then
                new_list.Add(list1(index1))
                new_list.Add(list2(index2))
                index1 = index1 + 1
                index2 = index2 + 1
            End If
        Loop

        ' Add left over items from the remaining list
        If index1 < list1.Count Then
            For item = index1 To list1.Count - 1
                new_list.Add(list1(item))
            Next
        ElseIf index2 < list2.Count Then
            For item = index2 To list2.Count - 1
                new_list.Add(list2(item))
            Next
        End If

        Return new_list
    End Function

    'Main algorithm starts here
    Sub Main()
        Dim items() As String = {"Florida", "Georgia", "Delaware", "Alabama", "California"}
        items = merge_sort(items)
        Console.WriteLine(String.Join(", ", items))
    End Sub
End Module